{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Graph contains cycle\n"
     ]
    }
   ],
   "source": [
    "# Python Program for union-find algorithm to detect cycle in a undirected graph\n",
    "# we have one egde for any two vertex i.e 1-2 is either 1-2 or 2-1 but not both\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "#This class represents a undirected graph using adjacency list representation\n",
    "class Graph:\n",
    "\n",
    "    def __init__(self,vertices):\n",
    "\t\tself.V= vertices #No. of vertices\n",
    "\t\tself.graph = defaultdict(list) # default dictionary to store graph\n",
    "\n",
    "\n",
    "\t# function to add an edge to graph\n",
    "\tdef addEdge(self,u,v):\n",
    "\t\tself.graph[u].append(v)\n",
    "\n",
    "\t# A utility function to find the subset of an element i\n",
    "\tdef find_parent(self, parent,i):\n",
    "\t\tif parent[i] == -1:\n",
    "\t\t\treturn i\n",
    "\t\tif parent[i]!= -1:\n",
    "\t\t\treturn self.find_parent(parent,parent[i])\n",
    "\n",
    "\t# A utility function to do union of two subsets\n",
    "\tdef union(self,parent,x,y):\n",
    "\t\tparent[x] = y\n",
    "\n",
    "\n",
    "\n",
    "\t# The main function to check whether a given graph\n",
    "\t# contains cycle or not\n",
    "\tdef isCyclic(self):\n",
    "\n",
    "\t\t# Allocate memory for creating V subsets and\n",
    "\t\t# Initialize all subsets as single element sets\n",
    "\t\tparent = [-1] * self.V\n",
    "\n",
    "\t\t# Iterate through all edges of graph, find subset of both\n",
    "\t\t# vertices of every edge, if both subsets are same, then\n",
    "\t\t# there is cycle in graph.\n",
    "\t\tfor i in self.graph:\n",
    "\t\t\tfor j in self.graph[i]:\n",
    "\t\t\t\tx = self.find_parent(parent, i)\n",
    "\t\t\t\ty = self.find_parent(parent, j)\n",
    "\t\t\t\tif x == y:\n",
    "\t\t\t\t\treturn True\n",
    "\t\t\t\tself.union(parent,x,y)\n",
    "\n",
    "\n",
    "# Create a graph given in the above diagram\n",
    "g = Graph(3)\n",
    "g.addEdge(0, 1)\n",
    "g.addEdge(1, 2)\n",
    "g.addEdge(2, 0)\n",
    "\n",
    "if g.isCyclic():\n",
    "\tprint (\"Graph contains cycle\")\n",
    "else :\n",
    "\tprint (\"Graph does not contain cycle \")\n",
    "\n",
    "#This code is contributed by Neelam Yadav"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
